import java.util.Deque;
import java.util.LinkedList;

/**
 * 面试题 03.04. 化栈为队
 * https://leetcode-cn.com/problems/implement-queue-using-stacks-lcci/
 */
public class Solutions_mianshi_03_04 {
    public static void main(String[] args) {
        MyQueue2 queue = new MyQueue2();
        queue.push(1);
        queue.push(2);
        int res1 = queue.peek();  // output: 1
        System.out.println(res1);
        int res2 = queue.pop();  // output: 1
        System.out.println(res2);
        boolean res3 = queue.empty();  // output: false
        System.out.println(res3);
    }
}

class MyQueue2 {
    private Deque<Integer> stack1;
    private Deque<Integer> stack2;

    /** Initialize your data structure here. */
    public MyQueue2() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.push(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (stack2.isEmpty()) {
            // stack1 中的元素“转移”到 stack2 中
            // 使得 stack1 中的栈顶元素成为 stack2 中的栈底元素
            // stack1 中的栈底元素，成为 stack2 中的栈顶元素
            // pop 与 peek 操作时，对 stack2 进行操作，从而实现队列效果：先进先出
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    /** Get the front element. */
    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack2.isEmpty() && stack1.isEmpty();
    }
}
